package gold.gold04;

/**
 * 首先定义一下数组的旋转, 旋转就是左右移动。。。如下, 就挺突然的。
 * https://blog.csdn.net/u012371712/article/details/79683390
 * 旋转能给一个数组带来怎样的变化?所以旋转n次和1次有什么区别?
 */
public class S1003搜索旋转数组 {
    /**
     * 100, 关于二分法, 中间值一直处理不好。这里就一直不用endPosi, 所以取midPosi的时候不用考虑太多。
     * 边界处理得比示范要好一点点。
     */
    public int search2(int[] arr, int target) {
        return binSearch(arr, target, 0, arr.length);
    }
    // endPosi是取不到的。
    private int binSearch(int[] arr, int target, int startPosi, int endPosi){
        //System.out.println(Arrays.toString(arr) + startPosi + "|" + endPosi);
        if(endPosi - startPosi <= 1) return arr[startPosi] == target? startPosi: -1;
        if(arr[startPosi] < arr[endPosi - 1]){
            // 这是一段递增的
            if(target > arr[endPosi - 1] || target < arr[startPosi]) return -1;
        }
        int midPosi = (endPosi + startPosi) / 2;
        int a = binSearch(arr, target, startPosi, midPosi);
        if(a != -1) return a;
        return binSearch(arr, target, midPosi, endPosi);
    }

    /**
     * 25, 遍历, 这样肯定不行的。
     */
    public int search(int[] arr, int target) {
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == target) return i;
        }
        return -1;
    }
}
